/*
   @Copyright:LintCode
   @Author:   tjyemail
   @Problem:  http://www.lintcode.com/problem/nuts-bolts-problem
   @Language: C++
   @Datetime: 19-04-03 11:01
   */

/**
 * class Comparator {
 *     public:
 *      int cmp(string a, string b);
 * };
 * You can use compare.cmp(a, b) to compare nuts "a" and bolts "b",
 * if "a" is bigger than "b", it will return 1, else if they are equal,
 * it will return 0, else if "a" is smaller than "b", it will return -1.
 * When "a" is not a nut or "b" is not a bolt, it will return 2, which is not valid.
 */

// Method 1, parition+quick sort, Time 2988ms
class Solution {
	int partition(vector<string> &vs, int begin, int end, string &key, Comparator comp){
		for(int i=begin; i<end;){
			const int cmp=comp.cmp(vs[i],key);
			const int rev=comp.cmp(key,vs[i]);
			if(cmp==-1 || rev==1) swap(vs[i++],vs[begin++]);
			else if(cmp==1 || rev==-1) swap(vs[i],vs[--end]);
			else if(cmp==0 || rev==0) ++i;
		}
		return begin;
	}
	void quicksort(vector<string> &nuts, vector<string> &bolts, int begin, int end, Comparator comp){
		if(begin>=end-1) return;
		int mid=partition(nuts,begin,end,bolts[begin],comp);
		partition(bolts,begin,end,nuts[mid],comp);
		quicksort(nuts,bolts,begin,mid,comp);
		quicksort(nuts,bolts,mid+1,end,comp);
	}
public:
	/**
	 * @param nuts: a vector of integers
	 * @param bolts: a vector of integers
	 * @param compare: a instance of Comparator
	 * @return: nothing
	 */
	void sortNutsAndBolts(vector<string> &nuts, vector<string> &bolts, Comparator compare) {
		// write your code here
		if(nuts.size()!=bolts.size()) return;
		quicksort(nuts,bolts,0,nuts.size(),compare);
	}
};

// Method 2, select sort,Time 2521ms
class Solution {
public:
	/**
	 * @param nuts: a vector of integers
	 * @param bolts: a vector of integers
	 * @param compare: a instance of Comparator
	 * @return: nothing
	 */
	void sortNutsAndBolts(vector<string> &nuts, vector<string> &bolts, Comparator compare) {
		// write your code here
		for(int i=0; i<nuts.size(); ++i){
			for(int j=i; j<bolts.size(); ++j){
				if(compare.cmp(nuts[i],bolts[j])==0){
					swap(bolts[i],bolts[j]);
					break;
				}
			}
		}
	}
};
